package Data_Structure.Queue;

/**
 * @className: MyQueue
 * @author: 芃
 * @description: 单链表模拟实现队列
 * @date: 2023/8/21 18:13
 */
//队列：先进先出
//普通队列：队尾进，对头出
//无论如何标记队头队尾，使用会有时间复杂度为O（N）的一项，即入队或出队
//区别于普通的单向链表，借助last指针指向队尾元素，插入时直接插入到队尾元素的后面，维护last指针始终指向队尾元素即可
//出队列时，直接将head指针指向的元素出出来，维护head指针始终指向头节点即可
public class MyQueue {
    private Node head;//头节点
    private Node last;//尾节点

    //插入元素-》入队->尾插法
    public void offer(int val){
        Node node = new Node(val);
        if (head == null){
            head = node;
            last = node;
        }else {
            last.next = node;
            last = last.next;
        }
    }
    //查看对头元素
    public Integer peek(){
        if (isEmpty()){
            return null;
        }
        return this.head.value;
    }
    //删除元素-》出队
    public Integer poll(){
        if (isEmpty()){
            return null;
        }
        Node ret = head;
        this.head = head.next;
        if (head == null){
            last = null;
        }
        return ret.value;
    }
    //判断队列为空
    public boolean isEmpty(){
        return this.head == null;
    }
}
